25. K 个一组翻转链表

Similar Question

leading to the advanced question

Solution Tips

方案一: 模拟

    reverseKGroup(k) {
        if (k === 0) return this.head;
        // 头插法
        // 每个 k 均用头插法实现, 然后不断更新头即可
        const dummyHead = new Node(0);
        dummyHead.next = this.head;

        let count = 0;
        let cur = dummyHead;
        let stickyHead = null;
        let subHead = null;
        let subTail = null;
        let subNext = null;

        while (cur !== null) {

            if (count + 1 === 1) {
                // 子链表翻转的起点
                // 更新子头
                stickyHead = cur;
                subHead = cur.next;
            }

            if (count === k) {
                // 子链表翻转的终点点
                subTail = cur;
                subNext = cur.next;
                subTail.next = null;
                // 发起一次子链表反转
                reverseListToPrev(stickyHead, subHead)

                // 子链表重新拼接尾部
                subHead.next = subNext;
                // 开启新的循环
                count = 0;
                cur = subHead
                continue
            }

            cur = cur.next;
            count++;
        }

        this.head = dummyHead.next;
        return dummyHead.next;

        function reverseListToPrev(stickyHead, head) {
            let cur = head;
            let prev = null;
            let next = null;

            while (cur !== null) {
                next = cur.next;
                cur.next = prev;

                // 更新固定的头引用
                stickyHead.next = cur;
                prev = cur;
                cur = next;

            }

            return stickyHead;
        }
    }
}

方案二: 头插法优化翻转